/*
Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9  20
/  \
15   7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}





class Solution {
public:

	vector<vector<int> > levelOrder(TreeNode *root) {

		vector<vector<int> > levelInt(0);
		queue<TreeNode*> queueTree;
		TreeNode *p = new TreeNode(-1);
		

		if (root == NULL)
		{
			return levelInt;
		}
		else
		{
			vector<int> intVec;
			intVec.push_back(root->val);
			levelInt.push_back(intVec);

			if (root->left != NULL)
			{
				queueTree.push(root->left);
			}
			if (root->right != NULL)
			{
				queueTree.push(root->right);
			}
			
			while (!queueTree.empty())
			{
				queue<TreeNode*> queueTreeNext;
				p = queueTree.front();
				
				intVec.clear();
				intVec.push_back(p->val);
				if (p->left != NULL)
				{
					queueTreeNext.push(p->left);

				}
				if (p->right!= NULL)
				{
					queueTreeNext.push(p->right);

				}
				queueTree.pop();
				while (!queueTree.empty())
				{
					p = queueTree.front();

				
					intVec.push_back(p->val);
					if (p->left != NULL)
					{
						queueTreeNext.push(p->left);

					}
					if (p->right != NULL)
					{
						queueTreeNext.push(p->right);

					}
					queueTree.pop();
				}

				levelInt.push_back(intVec);
				queueTree = queueTreeNext;

			}

			
		}
		return levelInt;
	}
};


class Solution2 {
public:
	vector<vector<int> > levelOrder(TreeNode *root) {
		// Start typing your C/C++ solution below  
		// DO NOT write int main() function  
		vector< vector<int> > result;
		if (root == NULL)
			return result;

		queue<TreeNode*> q;
		q.push(root);
		int count = 1;
		int level = 0;
		vector<int> tmp(0);
		while (!q.empty())
		{
			tmp.clear();
			level = 0;
			for (int i = 0; i < count; ++i)
			{
				root = q.front();
				q.pop();
				tmp.push_back(root->val);
				if (root->left != NULL)
				{
					q.push(root->left);
					++level;
				}
				if (root->right != NULL)
				{
					q.push(root->right);
					++level;
				}
			}
			count = level;
			result.push_back(tmp);
		}
		return result;
	}
};

int main(int argc, char* argv[])
{



	for (int i = 1; i < argc; i++){


		cout << argv[i] << endl;

	}

	int A[] = { 1, 2, 3, 0, 0 };
	int B[] = { 2, 4 };
	//cout << << endl;
	stack<int> st, st2;
	st.push(1);
	st.push(2);
	

	vector<vector<int> > levelInt(0);
	//stack<TreeNode*> stackTree;
	//vector<int> intVec;
	//intVec.push_back(1);
	//levelInt.push_back(intVec);


	TreeNode *p = new TreeNode(1);

	TreeNode *left = new TreeNode(2);
	TreeNode *right = new TreeNode(3);
	TreeNode *left1 = new TreeNode(4);
	TreeNode *right1 = new TreeNode(5);


	p->left = left;
	p->right = right;
	p->left->left = left1;
	p->left->right = NULL;
	p->right->right = right1;
	p->right->left = NULL;

	Solution s;
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	levelInt = s.levelOrder(p);
	
	system("pause");
	return 0;
}